package 纯数组;

import java.util.Arrays;

public class No31下一个排列 {

    /**
     * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
     * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
     * 必须 原地 修改，只允许使用额外常数空间。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3]
     * 输出：[1,3,2]
     * 示例 2：
     * 输入：nums = [3,2,1]
     * 输出：[1,2,3]
     * 示例 3：
     * 输入：nums = [1,1,5]
     * 输出：[1,5,1]
     * 示例 4：
     * 输入：nums = [1]
     * 输出：[1]
     */

    public void nextPermutation(int[] nums) {

        int index1 = -1;
        // 找到第一个降序元素,然后从后方找到一个第一个比它大的,然后交换
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                index1 = i;
                break;
            }
        }

        // 最大序列了
        if (index1 == -1) {
            Arrays.sort(nums);
        }

        // 再找到第一个比它大的,然后交换
        for (int i = nums.length - 1; i > index1; i--) {
            if (nums[i] > nums[index1]) {
                int temp = nums[index1];
                nums[index1] = nums[i];
                nums[i] = temp;
                break;
            }
        }

        // 后方排序
        Arrays.sort(nums, index1 + 1, nums.length);
    }

}